package com.test.leetcode;

/**
 * @Classname 接雨水
 * @Description TODO
 * @Date 2025/2/25 9:29
 * @Created by rgs
 */
public class 接雨水 {
    public static void main(String[] args) {
        int[] height = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }


    public static int trap(int[] height) {
        if (height == null || height.length < 1) {
            return 0;
        }

        int total = 0;
        for (int i = 1; i < height.length; i++) {
            // find left max num
            int lMax = 0;
            for (int m = 0; m < i; m++) {
                lMax = Math.max(height[m], lMax);
            }

            // find right max num
            int rMax = 0;
            for (int n = i + 1; n < height.length; n++) {
                rMax = Math.max(height[n], rMax);
            }

            // calc current element
            if (lMax != 0 && rMax != 0 && height[i] < lMax && height[i] < rMax) {
                // 两次边界的最小值减去当前位置的高度
                total = total + (Math.min(lMax, rMax) - height[i]);
            }
        }

        return total;

    }


    /**
     *
     * 代码分析，我们使用的是双层循环，时间复杂度是On2
     * 复杂在哪里，复杂在每次计算某个元素时，都要去遍历左侧和右侧
     * 思考：可不可以先把左侧右侧都计算出来，然后再遍历一次原始数组计算即可。
     * 这样就用三次On的循环代替了On2.
     *
     */

    public static int trap2(int[] height) {
        if (height == null || height.length < 1) {
            return 0;
        }

        int n = height.length;
        int total = 0;

        int[] lMax = new int[n];
        int[] rMax = new int[n];

        // 计算左侧
        lMax[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            // 比较当前位置与左侧区间的最大值，赋值给当前位置
            lMax[i] = Math.max(lMax[i - 1], height[i]);
        }

        // 计算右侧
        rMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rMax[i] = Math.max(rMax[i + 1], height[i]);
        }
        
        // 计算
        for (int i = 0; i < n; i++) {
            total +=  Math.min(lMax[i],rMax[i])-height[i];
        }

        return total;
    }
}
